#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<stack>
#include<assert.h>

using namespace std;

namespace my_vector
{
	template<class T>
	class vector{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
		iterator begin()
		{
			return start;
		}

		iterator end()
		{
			return finish;
		}

		const_iterator begin() const
		{
			return start;
		}

		iterator end() const
		{
			return finish;
		}

		size_t size() const
		{
			return finish - start;
		}
        
		size_t capacity() const
		{
			return end_of_storage - start;
		}
		bool empty() const
		{
			return start == finish;
		}

		vector():start(nullptr),finish(nullptr),end_of_storage(nullptr)//无参构造函数
		{};

		vector(size_t n, const T& val = T())
		{
			resize(n, val);
		}

		vector(int n, const T& val = T())
		{
			resize(n, val);
		}

		vector(const vector<T>& x)
		{
			reserve(x.capacity());//扩容
			resize(x.size());//改变size
			for (int i = 0; i < x.size(); ++i)
				*(start + i) = *(x.start + i);
		}

		template <class InputIterator>
		vector(InputIterator first, InputIterator last)//函数模板，区间初始化
		{
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}
		vector& operator= (const vector<T>& x)//赋值运算符重载
		{
			vector<T> tmp(x);
			swap(tmp);

			return *this;
		}
		void resize(size_t n, const T& val = T())
		{
			if (n > size())
			{
				reserve(n);
				while (finish < start + n)
				{
					*(finish++) = val;
				}
			}

			else
			{
				finish = start+n;
			}
		}
		void reserve(size_t n)
		{
			if (n > capacity())
			{
				T* tmp = new T[n];
				size_t old_size = size();

				if (start)
				{
					for (int i = 0; i < size(); ++i)
						tmp[i] = *(start + i);

					delete[] start;//释放原来的空间
				}
				start = tmp;
				finish = tmp + old_size;
				end_of_storage = tmp + n;
			}
		}

		T& operator[] (size_t n)
		{
			return *(start + n);
		}
		const T& operator[] (size_t n) const
		{
			return *(start + n);
		}
		
	
		void push_back(const T& val)
		{
			if (finish < end_of_storage)
			{
				*(finish++) = val;
			}
			else
			{
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 1.5;
				reserve(newcapacity);
				*(finish++) = val;
			}
		}

		void pop_back()
		{
			assert(start != finish);
			finish--;
		}

		iterator insert(iterator position, const T& val)
		{
			assert(position != nullptr);

			size_t pos = position - start;//先保存position指针离start的相对位置，防止后面会迭代器失效
			reserve(size() + 1);//不管需不需要扩容，先去调用一下扩容函数，如果需要扩容就会扩容，不需要就什么也不干


			for (int i = size(); i > pos; --i)//把所有的值后挪动一位
				(*this)[i] = (*this)[i - 1];

			(*this)[pos] = val;//插入
			finish++;

			return start + pos;
		}
		iterator erase(iterator position)
		{
			assert(position >= start);
			assert(position < finish);

			for (int i = position - start; i < size() - 1; ++i)//把pos位置后面的值往前覆盖
				(*this)[i] = (*this)[i+1];
			finish--;
			return position;
		}
		
		void shrink_to_fit()
		{
			if (capacity() > size())
			{
				int n = size();
				T* tmp = new T[n];
				for (int i = 0; i < size(); ++i)
					tmp[i] = (*this)[i];
				if(start)
				  delete[] start;
				start = tmp;
				finish = end_of_storage = tmp + n;
			}
		}
		

		void swap(vector& x)
		{
			std::swap(x.finish, finish);
			std::swap(x.start, start);
			std::swap(x.end_of_storage,end_of_storage);
		}

		void clear()
		{
			finish = start;
		}
		~vector()
		{
			delete[] start;
			start = finish = end_of_storage = nullptr;
		}

	private:
		iterator start;
		iterator finish;
		iterator end_of_storage;
	};

	template<class T>
	void swap(vector<T>& x, vector<T>& y)
	{
		x.swap(y);
	}

	void print_vector(const vector<int>& v)
	{
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}


	void test_vector1()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(4);
		v.push_back(4);
		v.push_back(4);

		vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

		v[0]++;
		for (size_t i = 0; i < v.size(); i++)
		{
			cout << v[i] << " ";
		}
		cout << endl;

		v.insert(v.begin(), 100);
		print_vector(v);

		v.insert(v.begin(), 100);
		print_vector(v);

		int i = 0;
		int j = int();
		int k = int(10);
	}

	void test_vector2()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(4);
		v.push_back(4);

		vector<int> v1 = v;

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

		vector<int> v2;
		v2.push_back(11);
		v2.push_back(21);
		v2.push_back(31);
		v2.push_back(411);
		v2.push_back(41);
		v2.push_back(41);

		v1 = v2;
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;
	}


	void test_vector4()
	{
		vector<string> v;
		v.reserve(10);
		v.push_back("xxxx");
		v.push_back("xxxx");
		v.push_back("xxxx");
		v.push_back("xxxx");
		v.push_back("xxxx");
		v.push_back("xxxx");

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

		v.resize(8);
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

		v.resize(15, "yyyy");
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

		v.resize(3);
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void test_vector5()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
		v.push_back(6);

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

		v.erase(v.begin() + 3);

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	// 迭代器失效
	void test_vector6()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(4);
		v.push_back(4);
		v.push_back(5);
		v.push_back(6);
		//v.push_back(7);

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

		// 要求删除所有的偶数
		vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			if (*it % 2 == 0)
			{
				it = v.erase(it);
			}
			else
			{
				++it;
			}
		}

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void test_vector7()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
		v.push_back(6);
		v.push_back(7);
		v.push_back(8);
		v.push_back(9);

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;


		vector<string> vstr;
		vstr.push_back("1111");
		vstr.push_back("1111");
		vstr.push_back("1111");
		vstr.push_back("1111");
		vstr.push_back("1111");

		for (auto e : vstr)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void test_vector8()
	{
		/*vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(5);

		vector<int> v2(v1.begin(), v1.end());
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;

		list<int> lt;
		lt.push_back(10);
		lt.push_back(20);
		lt.push_back(30);
		lt.push_back(40);
		vector<int> v3(lt.begin(), lt.end());
		for (auto e : v3)
		{
			cout << e << " ";
		}
		cout << endl;

		int a[] = { 100, 200, 300 };
		vector<int> v4(a, a+3);
		for (auto e : v4)
		{
			cout << e << " ";
		}
		cout << endl;*/
	}

	void test_vector9()
	{
		vector<string> v1(5, "1111");
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

		vector<int> v2(5, 1);
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}